/*
Array.h, contains class Array.
Encapsulate a normal array.
See the definition below for detail
Author: NianchenDeng (5080379114)
*/

#pragma once
#ifndef uint
#define uint unsigned int
#endif

#ifndef IN
#define IN
#endif
#ifndef OUT
#define OUT
#endif
#ifndef INOUT
#define INOUT
#endif

template <class _Ty>
class Array
{
private:
  _Ty *_Arr;
  mutable uint _Size;
  uint _Capacity;
  void alloc_new_space ()                                                   // Double the space
  {
    if (_Capacity == 0)
      _Capacity = 1;
    _Capacity *= 2;
    _Ty *temp = new _Ty[_Capacity];
    for (uint i = 0; i < _Size; ++i)
    {
      temp[i] = _Arr[i];
    }
    delete [] _Arr;
    _Arr = temp;
  }
public:
	Array (int capcity = 1) : _Size (0), _Capacity (capcity)
	{
    if (_Capacity == 0) _Capacity = 1;
		_Arr = new _Ty[_Capacity];
	}
	Array (const Array <_Ty> &source) : _Capacity (source._Size)
	{
		_Arr = new _Ty[_Capacity];
		*this = source;                                                         // --Call assign operator
	}
	~Array ()
	{
		delete []_Arr;
	}

	Array &operator= (const Array <_Ty> &right)                               // Assign operator
	{
		_Size = right._Size;
		if (_Capacity < right._Size)                                            // --When no enough space, allocate new
		{
			delete [] _Arr;
			_Capacity = right._Size;
      if (_Capacity = 0) _Capacity = 1;
			_Arr = new _Ty[_Capacity];
		}
		for (uint i = 0; i < _Size; ++i)                                        // --Copy data
		{
			_Arr[i] = right._Arr[i];
		}
		return (*this);
	}
	_Ty &operator[] (uint pos) const                                          // Get element by index
	{
		if (pos >= _Capacity)
			throw "Out of Range.";
    if (pos >= _Size)
    {
      for (uint i = _Size; i <= pos; ++i)
        _Arr[i] = _Ty ();
      _Size = pos + 1;
    }
		return _Arr[pos];
	}
	uint size () const
	{
		return _Size;
	}
	uint capacity ()
	{
		return _Capacity;
	}
	bool insert (const _Ty &elem, uint pos)
	{
		if (pos >= _Size)
			return false;
		if (_Size == _Capacity)                                                 // --No space left. alloc new
			alloc_new_space ();
		for (uint i = _Size; i > pos; --i)
			_Arr[i] = _Arr[i - 1];
		_Arr[pos] = elem;
		++_Size;
		return true;
	}
	bool erase (uint pos)
	{
		if (pos >= _Size)
			return false;
		--_Size;
		for (uint i = pos; i < _Size; ++i)
			_Arr[i] = _Arr[i + 1];
		return true;
	}
	bool push_back (const _Ty &elem)
	{
		if (_Size == _Capacity)
			alloc_new_space ();
		_Arr[_Size++] = elem;
		return true;
	}
	bool pop_back ()
	{
		if (_Size == 0)
			return false;
		--_Size;
		return true;
	}
	int find_first_of (const _Ty &elem) const                                 // Return -1 if not find
	{
		for (uint i = 0; i < _Size; ++i)
			if (_Arr[i] == elem)
				return i;
		return -1;
	}
	int find_last_of (const _Ty &elem) const                                  // Return -1 if not find
	{
		for (uint i = _Size; i > 0; --i)
			if (_Arr[i - 1] == elem)
				return i - 1;
		return -1;
	}
  void clear ()
  {
    _Size = 0;
  }
  void resize (uint new_size)
  {
    while (new_size > _Capacity)
      alloc_new_space ();
    for (uint i = _Size; i < new_size; ++i)
      _Arr[i] = _Ty ();
    _Size = new_size;
  }
};